{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 96. 不同的二叉搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？\n",
    "\n",
    "示例:\n",
    "\n",
    "输入: 3\n",
    "输出: 5\n",
    "解释:\n",
    "给定 n = 3, 一共有 5 种不同结构的二叉搜索树:\n",
    "```\n",
    "   1         3     3      2      1\n",
    "    \\       /     /      / \\      \\\n",
    "     3     2     1      1   3      2\n",
    "    /     /       \\                 \\\n",
    "   2     1         2                 3\n",
    "```\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/unique-binary-search-trees\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "二叉搜索树:左节点<中间的节点<右节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "通过上面的例子可以看出\n",
    "\n",
    "G(n) 表示n个节点存在二叉搜索树的的数量\n",
    "\n",
    "f(i,n): 以 i 为根、序列长度为 n 的不同二叉搜索树个数 (1 <= i <= n)。\n",
    "\n",
    "$$\n",
    "G(n) = \\sum_{i=1}^{n} G(i-1)*G(n-i)\n",
    "$$\n",
    "\n",
    "边界情况\n",
    "\n",
    "G(0) = 1 \n",
    "\n",
    "\n",
    "G(1) = 1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "举个例子\n",
    "\n",
    "创建以3为根长度7的二叉树搜索树\n",
    "\n",
    "左节点为 `1,2`, 右节点为`4,5,6,7`\n",
    "\n",
    "F(3, 7) = G(2) * G(4)\n",
    "\n",
    "可以得到\n",
    "\n",
    "$$\n",
    "F(i,n) =  G(i-1)*G(n-i)\n",
    "$$\n",
    "\n",
    "$$\n",
    "G(n) = \\sum_{i=1}^{n} F(i,n)\n",
    "$$\n",
    "\n",
    "$$\n",
    "G(n) = \\sum_{i=1}^{n} G(i-1)*G(n-i)\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 吐血,答案还是抄的\n",
    "class Solution:\n",
    "    def numTrees(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        g = [0] * (n+1)\n",
    "        g[0], g[1] = 1, 1\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(i+1):\n",
    "                g[i] += g[j-1] * g[i-j]\n",
    "                \n",
    "        return g[n]\n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "429"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Solution().numTrees(7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
